home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / basic / iqb9202.zip / SENTINEL.BAS < prev    next >
BASIC Source File  |  1992-01-02  |  2KB  |  81 lines
  1. CONST EndOfList = 5000
  2. ' $INCLUDE: 'QTIMER.BI'
  3.  
  4. DIM RandoList(EndOfList) AS INTEGER
  5. DECLARE FUNCTION RanMan% (Range AS INTEGER)
  6.  
  7. RANDOMIZE TIMER
  8.  
  9. PRINT "Create the random list of numbers"
  10.  
  11. FOR I% = 0 TO EndOfList%
  12.    RandoList(I%) = I%
  13. NEXT I%
  14.  
  15. FOR I% = 0 TO EndOfList
  16.    Idx% = RanMan%(EndOfList)
  17.    Tmp% = RandoList(I%)
  18.    RandoList(I%) = RandoList(Idx%)
  19.    RandoList(Idx%) = Tmp%
  20. NEXT I%
  21.  
  22. PRINT "Normal linear search"
  23.  
  24. Count& = 0
  25. Misses% = 0
  26. StartTime& = tStart&
  27.  
  28. FOR I% = 0 TO EndOfList + 5
  29.    J% = 0
  30.    DO WHILE ((RandoList(J%) <> I%) AND (J% < EndOfList))
  31.      J% = J% + 1
  32.    LOOP
  33.    IF J% = EndOfList THEN
  34.      Misses% = Misses% + 1
  35.    ELSE
  36.      Count& = Count& + J%
  37.    END IF
  38. NEXT I%
  39.  
  40. EndTime& = tGet&
  41.  
  42. fpCount& = Count&
  43. fpExp! = (EndOfList + 5 - Misses%)
  44.  
  45. PRINT "Time: "; tFormat$(StartTime&, EndTime&);
  46. PRINT USING " Average searches: #####.###"; fpCount& / fpExp!;
  47. PRINT " Misses: "; Misses%
  48.  
  49. PRINT "Linear search using a sentinel value"
  50.  
  51. Count& = 0
  52. Misses% = 0
  53. StartTime& = tStart&
  54.  
  55. FOR I% = 0 TO EndOfList + 5
  56.    RandoList(EndOfList) = I%
  57.    J% = 0
  58.    DO WHILE RandoList(J%) <> I%
  59.      J% = J% + 1
  60.    LOOP
  61.    IF J% = EndOfList THEN
  62.      Misses% = Misses% + 1
  63.    ELSE
  64.      Count& = Count& + J%
  65.    END IF
  66. NEXT I%
  67.  
  68. EndTime& = tGet&
  69. fpCount& = Count&
  70. fpExp! = (EndOfList + 5 - Misses%)
  71.  
  72. PRINT "Time: "; tFormat$(StartTime&, EndTime&);
  73. PRINT USING " Average searches: #####.###"; fpCount& / fpExp!;
  74. PRINT " Misses: "; Misses%
  75.  
  76. PRINT "End of execution"
  77.  
  78. FUNCTION RanMan% (Range AS INTEGER)
  79. RanMan% = INT((Range - 1 + 1)*RND +1)
  80. END FUNCTION
  81.